{{{id=1|
#generating all possible lengths of cycles on 20 vertices, ascending order
types=[]
for k in range(1,7):
    d=[0]*k
    m=int(11-3*k/2)
    pp=m^(k-1)
    for i in range(pp):
        ii=i
        d[k-1]=20-3*k
        for j in range(k-1):
            d[j]=int(ii)%int(m)
            ii=ii//m
            d[k-1]-=(k-j)*d[j]
        if d[k-1]>=0:
            ii=3
            res=[]
            for j in range(k):
                ii+=d[j]
                res.append(ii)
            types.append(res)

#list of alternating 0s and 1s of given length
def alt_gen(k):
    alt = [1]*k
    for i in range((k-1)/2+1):
        alt[2*i]=0
    return alt

#appending some info to res: pair of numbers of edges in the two components, alternating sequence with duplications at given positions
#dups is a non-decreasing sequence of indexes, may be empty
def duplicate(res,dups,nn):
    if nn<=0:
        return 0
    alt = alt_gen(nn)
    for i in range(len(dups)):
        alt.insert(i+dups[i],alt[i+dups[i]])
    x=0 #counter for consecutive 0s (cyclic)
    y=0 #1s
    for i in range(len(alt)-1):
        if alt[i]==0 and alt[i+1]==0:
            x+=1
        if alt[i]==1 and alt[i+1]==1:
            y+=1
	if alt[0]==0 and alt[len(alt)-1]==0:
		x+=1
	if alt[0]==1 and alt[len(alt)-1]==1:
		y+=1
    if x>3 or y>3:
        return 0 #no need of 3 or more
    res.append([x,y])
    res.append(alt)
    if x!=y: #isomorphic if x=y, otherwise we also add with 0<->1 interchanged
        alt=[1-i for i in alt]
        res.append([y,x])
        res.append(alt)
    return 0

#generates all (up to cyclic translation) lists of 0s and 1s of length n with no more than three cyclic occurences of 00 and 11, each would correspond to an edge in H_1 or H_2
#have to call duplicate at all possible "dups" sets, up to cyclic translation
#let 0=g_0<=g_1<=...<=g_k be the positions to be duplicated
#the positions have values in 0,...,n-k-2
#can assume that the first index g_0=0, and the distance between first and second g_1-g_0 is smallest cyclically, i.e. g_{j+1}-g_j>=g_1-g_0=g_1
#g_k<=n-k-2 if g_1=0
#g_k<=n-k-1-g_1 if g_1>=1
#so we introduce gg=min(1,g_1)
#then g_k<=n-k-2+gg-g_1, g_{k-1}<=n-k-2+gg-2*g_1, etc.
#g_1<=n-k-2+gg-k*g_1, so g_1<=(n-k-1)/(k+1)
#more than six elements in dups will clearly return empty result, so k<=5
def enum_gen(n):
    res = []
    duplicate(res,[],n)
    duplicate(res,[0],n-1)
    for g1 in range(0,(n-2)/2+1):
        duplicate(res,[0,g1],n-2)
    for g1 in range(0,(n-3)/3+1):
        gg=min(1,g1)
        for g2 in range(2*g1,n-4+gg-g1):
            duplicate(res,[0,g1,g2],n-3)
    for g1 in range(0,(n-4)/4+1):
        gg=min(1,g1)
        for g2 in range(2*g1,n-5+gg-2*g1):
            for g3 in range(g2+g1,n-5+gg-g1):
                duplicate(res,[0,g1,g2,g3],n-4)
    for g1 in range(0,(n-5)/5+1):
        gg=min(1,g1)
        for g2 in range(2*g1,n-6+gg-3*g1):
            for g3 in range(g2+g1,n-6+gg-2*g1):
                for g4 in range(g3+g1,n-6+gg-g1):
                    duplicate(res,[0,g1,g2,g3,g4],n-5)
    for g1 in range(0,(n-6)/6+1):
        gg=min(1,g1)
        for g2 in range(2*g1,n-7+gg-4*g1):
            for g3 in range(g2+g1,n-7+gg-3*g1):
                for g4 in range(g3+g1,n-7+gg-2*g1):
                    for g5 in range(g4+g1,n-7+gg-g1):
                        duplicate(res,[0,g1,g2,g3,g4,g5],n-6)
    return res

eg = [enum_gen(n) for n in range(3,21)]

#srg(76,30,8,14)
p=-4/15
q=7/45

#Gramm matrix of a given double list
def GMat(A):
    n = len(A)
    B = Matrix([[q+(p-q)*A[i][j] for j in range(n)] for i in range(n)])
    for i in range(n):
        B[i,i]=1
    return B

#check if positive definite
def mineig(A):
    sp = A.eigenvalues()
    mv = sp[0]
    for v in sp:
        if v<mv:
            mv=v
    return mv

#double list of incidence of given type and enumeration, ex:[4,16],[[0,1,..],[1,0,...]]
def ttm(type,colors):
    res = [[0 for i in range(20)] for j in range(20)]
    n = len(type)
    ind = [0] #indexes for blocks defined by type
    k = 0
    for i in type:
        k += i
        ind.append(k)
    #generating enumeration
    color = [0]*20
    for i in range(n):
        for j in range(len(colors[i])):
            color[ind[i]+j]=colors[i][j]
    #all non-edges between diff colors
    for i in range(19):
        for j in range(i+1,20):
            if color[i]!=color[j]:
                res[i][j]=1
                res[j][i]=1
    #inverting edges between H_1 and H_2
    for i in range(n):
        j1 = ind[i]
        j2 = ind[i+1]-1
        res[j1][j2]=1-res[j1][j2]
        res[j2][j1]=1-res[j2][j1]
        for j in range(j1,j2):
            res[j][j+1]=1-res[j][j+1]
            res[j+1][j]=1-res[j+1][j]
    return res

 
#main loop    
html('<!--notruncate-->')
total_graphs = 0
for type in types:
    n = len(type)
    nn = [len(eg[k-3])/2 for k in type]
    pp = 1
    for a in nn:
        pp *= a
    print "type ", type
    ii = [0]*n
    fe = 0
    fr = 0
    fp = 0
    for i in range(pp):
        k = i
        for j in range(n):
            ii[j] = int(k) % int(nn[j])
            k = k//nn[j]
        x = 0
        y = 0
        for j in range(n):
            x += eg[type[j]-3][2*ii[j]][0] 
            y += eg[type[j]-3][2*ii[j]][1]
        if x>3 or y>3 or x!=y:
            fe += 1
        else:
            M = GMat(ttm(type,[eg[type[j]-3][2*ii[j]+1] for j in range(n)]))
            r = M.rank()
            if r>16:
                fr += 1
            else:
                mev = mineig(M)
                if mev<0:
                    fp += 1
                else:
                    print "through: ",type,[eg[type[j]-3][2*ii[j]+1] for j in range(n)],r,mev
    print "graphs:", pp-fe 
    total_graphs += (pp-fe)
    print "failed by rank:", fr 
    print "failed by posdef:", fp

print "Graphs (matrices) checked:", total_graphs
	
################################

#checking double lists of incidence of given type and enumeration, with all possibilities of adding 21st vertex, up to 3 edges to each half
def min_rank_ttma(type,colors):
    total_graphs = 0
    res = [[0 for i in range(21)] for j in range(21)]
    n = len(type)
    ind = [0] #indexes for blocks defined by type
    k = 0
    for i in type:
        k += i
        ind.append(k)
    #generating enumeration
    color = [0]*20
    for i in range(n):
        for j in range(len(colors[i])):
            color[ind[i]+j]=colors[i][j]
    #all non-edges between diff colors
    for i in range(19):
        for j in range(i+1,20):
            if color[i]!=color[j]:
                res[i][j]=1
                res[j][i]=1
    #inverting edges between H_1 and H_2
    for i in range(n):
        j1 = ind[i]
        j2 = ind[i+1]-1
        res[j1][j2]=1-res[j1][j2]
        res[j2][j1]=1-res[j2][j1]
        for j in range(j1,j2):
            res[j][j+1]=1-res[j][j+1]
            res[j+1][j]=1-res[j+1][j]
    #no edges
    minr = GMat(res).rank()
    total_graphs += 1
    #one edge
    for i in range(10):
        for j in range(10,20):
            for ic in range(20):
                res[20][ic]=0
                res[ic][20]=0
            res[20][i]=1
            res[i][20]=1
            res[20][j]=1
            res[j][20]=1
            rr = GMat(res).rank()
            total_graphs += 1
            if rr<minr:
                minr=rr
                if rr==16:
                    print type,colors,i,j
    #two edges
    for i1 in range(9):
        for i2 in range(i1+1,10):
            for j1 in range(10,19):
                for j2 in range(j1+1,20):
                    for ic in range(20):
                        res[20][ic]=0
                        res[ic][20]=0
                    res[20][i1]=1
                    res[i1][20]=1
                    res[20][j1]=1
                    res[j1][20]=1
                    res[20][i2]=1
                    res[i2][20]=1
                    res[20][j2]=1
                    res[j2][20]=1
                    rr = GMat(res).rank()
                    total_graphs += 1
                    if rr<minr:
                        minr=rr
                        if rr==16:
                            print type,colors,i1,i2,j1,j2
    #three edges
    for i1 in range(8):
        for i2 in range(i1+1,9):
            for i3 in range(i2+1,10):
                for j1 in range(10,18):
                    for j2 in range(j1+1,19):
                        for j3 in range(j2+1,20):
                            for ic in range(20):
                                res[20][ic]=0
                                res[ic][20]=0
                            res[20][i1]=1
                            res[i1][20]=1
                            res[20][j1]=1
                            res[j1][20]=1
                            res[20][i2]=1
                            res[i2][20]=1
                            res[20][j2]=1
                            res[j2][20]=1
                            res[20][i3]=1
                            res[i3][20]=1
                            res[20][j3]=1
                            res[j3][20]=1
                            rr = GMat(res).rank()
                            total_graphs += 1
                            if rr<minr:
                                minr=rr
                                if rr==16:
                                    print type,colors,i1,i2,i3,j1,j2,j3
    return total_graphs, minr


print min_rank_ttma([4,4,4,4,4],[[0,1,0,1],[0,1,0,1],[0,1,0,1],[0,1,0,1],[0,1,0,1]])
print min_rank_ttma([4,4,4,4,4],[[0,0,1,1],[0,1,0,1],[0,1,0,1],[0,1,0,1],[0,1,0,1]])
print min_rank_ttma([4,4,4,4,4],[[0,0,1,1],[0,0,1,1],[0,1,0,1],[0,1,0,1],[0,1,0,1]])
print min_rank_ttma([4,4,4,4,4],[[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,1,0,1],[0,1,0,1]])
///
<html><font color='black'><!--notruncate--></font></html>
type  [20]
graphs: 635
failed by rank: 635
failed by posdef: 0
type  [3, 17]
graphs: 450
failed by rank: 450
failed by posdef: 0
type  [4, 16]
graphs: 312
failed by rank: 312
failed by posdef: 0
type  [5, 15]
graphs: 260
failed by rank: 260
failed by posdef: 0
type  [6, 14]
graphs: 233
failed by rank: 233
failed by posdef: 0
type  [7, 13]
graphs: 204
failed by rank: 204
failed by posdef: 0
type  [8, 12]
graphs: 152
failed by rank: 152
failed by posdef: 0
type  [9, 11]
graphs: 184
failed by rank: 184
failed by posdef: 0
type  [10, 10]
graphs: 145
failed by rank: 145
failed by posdef: 0
type  [3, 3, 14]
graphs: 130
failed by rank: 130
failed by posdef: 0
type  [4, 4, 12]
graphs: 160
failed by rank: 160
failed by posdef: 0
type  [5, 5, 10]
graphs: 50
failed by rank: 50
failed by posdef: 0
type  [6, 6, 8]
graphs: 87
failed by rank: 87
failed by posdef: 0
type  [3, 4, 13]
graphs: 190
failed by rank: 190
failed by posdef: 0
type  [4, 5, 11]
graphs: 110
failed by rank: 110
failed by posdef: 0
type  [5, 6, 9]
graphs: 76
failed by rank: 76
failed by posdef: 0
type  [6, 7, 7]
graphs: 72
failed by rank: 72
failed by posdef: 0
type  [3, 5, 12]
graphs: 76
failed by rank: 76
failed by posdef: 0
type  [4, 6, 10]
graphs: 119
failed by rank: 119
failed by posdef: 0
type  [5, 7, 8]
graphs: 52
failed by rank: 52
failed by posdef: 0
type  [3, 6, 11]
graphs: 128
failed by rank: 128
failed by posdef: 0
type  [4, 7, 9]
graphs: 96
failed by rank: 96
failed by posdef: 0
type  [3, 7, 10]
graphs: 72
failed by rank: 72
failed by posdef: 0
type  [4, 8, 8]
graphs: 90
failed by rank: 90
failed by posdef: 0
type  [3, 8, 9]
graphs: 84
failed by rank: 84
failed by posdef: 0
type  [3, 3, 3, 11]
graphs: 82
failed by rank: 82
failed by posdef: 0
type  [4, 4, 4, 8]
graphs: 98
failed by rank: 98
failed by posdef: 0
type  [5, 5, 5, 5]
graphs: 14
failed by rank: 14
failed by posdef: 0
type  [3, 4, 4, 9]
graphs: 88
failed by rank: 88
failed by posdef: 0
type  [4, 5, 5, 6]
graphs: 42
failed by rank: 42
failed by posdef: 0
type  [3, 5, 5, 7]
graphs: 26
failed by rank: 26
failed by posdef: 0
type  [3, 3, 4, 10]
graphs: 74
failed by rank: 74
failed by posdef: 0
type  [4, 4, 5, 7]
graphs: 56
failed by rank: 56
failed by posdef: 0
type  [3, 4, 5, 8]
graphs: 46
failed by rank: 46
failed by posdef: 0
type  [3, 5, 6, 6]
graphs: 48
failed by rank: 48
failed by posdef: 0
type  [3, 3, 5, 9]
graphs: 48
failed by rank: 48
failed by posdef: 0
type  [4, 4, 6, 6]
graphs: 93
failed by rank: 93
failed by posdef: 0
type  [3, 4, 6, 7]
graphs: 64
failed by rank: 64
failed by posdef: 0
type  [3, 3, 6, 8]
graphs: 62
failed by rank: 62
failed by posdef: 0
type  [3, 3, 7, 7]
graphs: 42
failed by rank: 42
failed by posdef: 0
type  [3, 3, 3, 3, 8]
graphs: 58
failed by rank: 58
failed by posdef: 0
type  [4, 4, 4, 4, 4]
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 0, 1, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 0, 1, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 1, 0, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 0, 1, 1]] 16 0
through:  [4, 4, 4, 4, 4] [[0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]] 16 0
graphs: 106
failed by rank: 80
failed by posdef: 10
type  [3, 4, 4, 4, 5]
graphs: 50
failed by rank: 50
failed by posdef: 0
type  [3, 3, 4, 4, 6]
graphs: 66
failed by rank: 66
failed by posdef: 0
type  [3, 3, 3, 4, 7]
graphs: 48
failed by rank: 48
failed by posdef: 0
type  [3, 3, 4, 5, 5]
graphs: 28
failed by rank: 28
failed by posdef: 0
type  [3, 3, 3, 5, 6]
graphs: 42
failed by rank: 42
failed by posdef: 0
type  [3, 3, 3, 3, 3, 5]
graphs: 20
failed by rank: 0
failed by posdef: 20
type  [3, 3, 3, 3, 4, 4]
graphs: 58
failed by rank: 0
failed by posdef: 58
Graphs (matrices) checked: 5526
(16526, 17)
(16526, 17)
(16526, 17)
(16526, 17)
}}}

{{{id=3|

///
}}}

{{{id=2|

///
}}}